"""
A Python implementation of the Two-order Markov model to predict 
users next access domain in a session.

"""
import fileinput

def two_marov(train_dataset_path ,test_dataset_path,no_of_recommendation,mode_of_learning):
    markov_dic={}
    rec_count=0
    accuracy=0
    session_count=0
    no_of_request=0
    no_request=0
    
    for session in fileinput.input([train_dataset_path]):
        try:
            session_count=session_count+1
            markov_dic=train(session,session_count,markov_dic)
        except:
            continue
    for session in fileinput.input([test_dataset_path]):
        try:
            accuracy,rec_count,no_of_request,no_request=test(session,session_count,accuracy,rec_count,markov_dic,no_of_request,no_request,no_of_recommendation)
            if (mode_of_learning=='c'):
                markov_dic=train(session,session_count,markov_dic)
        except:
                continue
                
def train(session, session_count,markov_dic):
    '''
     #The following method u is used to train the session and the out put is 
     the transition matrix of two-order markov model as a dictionary based data structure
    '''
    total_frequency=0
    frequency=0

    session= session.strip().rstrip(',')
    session_elements=session.split(',')
    session_length=len(session_elements)-2
    for index in range(0,session_length):
        j=index+1
        k=j+1
        if markov_dic.has_key(session_elements[index]):
            value_markov=markov_dic.get(session_elements[index])
            total_frequency=value_markov[0]
            second_element_dic=value_markov[1]
            total_frequency=int(total_frequency)+1
            if second_element_dic.has_key(session_elements[j]):
                value_second=second_element_dic.get(session_elements[j])
                frequency=value_second[0]
                frequency=int(frequency)+1
                inner_dic=value_second[1]
                second_element_dic[session_elements[j]]=int(second_element_dic.get(session_elements[j]))+1
                if session_length>=1:
                    if inner_dic.has_key(session_elements[k]):
                        inner_dic[session_elements[k]]=int(inner_dic.get(session_elements[k]))+1
                    else:
                        inner_dic[session_elements[k]]=1
                        second_element_dic[session_elements[k]]=(frequency,inner_dic)
                    
            else:
                second_element_dic[session_elements[j]]=1
                markov_dic[session_elements[index]]=(total_frequency,second_element_dic)
                if session_length>=1:
                    inner_dic[session_elements[k]]=1
                    second_element_dic[session_elements[j]]=(frequency,inner_dic)
        else:
            total_frequency=1
            inner_frequency=1
            inner_dic={}
            second_element_dic={}
            inner_dic[session_elements[j]]=1
            markov_dic[session_elements[index]]=(total_frequency,inner_dic)
            if session_length>=1:
                second_element_dic=(markov_dic.get(session_elements[index]))[1]

                second_element_dic[session_elements[k]]=1
                second_element_dic[session_elements[j]]=(inner_frequency,second_element_dic)

    return markov_dic
    
def test(session,session_count,accuracy,rec_count,markov_dic,no_of_request,no_request,no_of_recommendation):
    '''
    This method will be used for testing  the incoming session 
    '''
    recommendation_list=[]
    session= session.strip().rstrip(',')
    session_elements=session.split(',')
    length=len(session_elements)-1
    for index in range(0,length):
        no_of_request+=1
        j=index+1
        if(length>=2):
            k=index+2
        else:
            k=index+1
        recommendation_list=recommend(index,session_elements[index],session_elements[j],markov_dic,no_of_recommendation)
        rec_length=len(recommendation_list)
        if rec_length==0:
            no_request+=1
        else:
            rec_count+=1
            j=index+1
            evaluation_results=evaluate(recommendation_list,session_elements[k],rec_count,accuracy)   
            accuracy=evaluation_results[0]      
    coverage=float(no_of_request-no_request)/float(no_of_request)*100
    print "Average:", accuracy
    print "Coverage:",coverage
    return accuracy,rec_count,no_of_request,no_request


def recommend(index,first_domain,second_domain,markov_dic,no_of_recommendations):
    '''
    This method will recommend the domains based on the transition probability matrix(markov_dic)
    and the number of recommendations can be limited by the use of parameter no_of_recommendation
    Returns a list of recommendations
    '''
    recommendation_list =[]
    outer_dic={}
    if (index==0):
        outer_tuple=markov_dic.get(first_domain)
        outer_dic= outer_tuple[1]
        if (outer_tuple==None):
            return recommendation_list
    else:
        inner_tuple=markov_dic.get(first_domain)
        second_element_dic=inner_tuple[1]
        if (inner_tuple==None):
            return recommendation_list
        inner_dic=second_element_dic.get(second_domain)
        outer_dic=inner_dic[1]
        if (inner_dic==None):
            return recommendation_list
    recommendation_list=sorted(outer_dic.iteritems(), key=lambda (k,v): (v,k))
    recommendation_list.reverse()
    length_of_rec=len(recommendation_list)
    results_list=[]
    for u in range(0,length_of_rec):
        results_list.append((recommendation_list[u])[0])
    return results_list[0:int(no_of_recommendations)]


def evaluate(recommendationlist,actual,rec_count,accuracy):
    '''
    This method is used to evaluate the recommendations generated by the recommend function
    returns accuracy and recommendation count
    '''

    if actual in recommendationlist:
        accuracy = calculate_accuracy(1,accuracy,rec_count)
        return (accuracy,rec_count)
    else:
        accuracy=calculate_accuracy(0,accuracy,rec_count)
        return (accuracy,rec_count)
    
def calculate_accuracy(correct,accuracy,rec_count):
    '''
    This method is used to calculate accuracy 
    '''
    return ((int(rec_count)-1)*float(accuracy)+int(correct))/int(rec_count)


if __name__ == "__main__": two_marov('D:\\train_d.csv','D:\\test_d.csv',20,'c')

